package cn.zhaoyuening.algorithms.dynamic;

/**
 * Created by Buynow on 2017/8/11.
 一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。
 输入描述:
 输入包括两行：
 第一行为整数n(1 ≤ n ≤ 50)
 第二行为n个整数length[i](1024 ≤ length[i] ≤ 4194304)，表示每个任务的长度为length[i]kb，每个数均为1024的倍数。


 输出描述:
 输出一个整数，表示最少需要处理的时间

 输入例子1:
 5
 3072 3072 7168 3072 1024

 输出例子1:
 9216
 */
public class MKP {
    public static void helper(int[] times) {
        int sum = 0;
        for (int time :
                times) {
            sum+=time;
        }

        int avgTime = sum/2;
        Integer[][] maxTimeArr = new Integer[times.length+1][avgTime+1];
        int r = getMaxTime(maxTimeArr, times, times.length, avgTime);
        int maxTime = Math.max(r,sum -r);
        System.out.println(maxTime);
    }

    public static int getMaxTime(Integer[][] maxTimeArr,int[] times,int n,int rTime){
        Integer maxTime = maxTimeArr[n][rTime];
        if ( maxTime != null) {
            return maxTime;
        }

        int time = times[n - 1];

        if (n == 1) {
            if (time > rTime) {
                maxTimeArr[n][rTime] = 0;
                return 0;
            }else{
                maxTimeArr[n][rTime] = time;
                return time;
            }
        }

        if (time > rTime) {
            maxTimeArr[n][rTime] = getMaxTime(maxTimeArr, times, n - 1, rTime);
            return maxTimeArr[n][rTime];
        }


        maxTimeArr[n][rTime] = Math.max(getMaxTime(maxTimeArr, times, n - 1, rTime),getMaxTime(maxTimeArr, times, n - 1, rTime-time)+time);
        return maxTimeArr[n][rTime];
    }

    public static void main(String[] args) {
        int[] times = new int[]{3072,3072,7168,3072,1024};
        helper(times);
    }
}
